# coding: utf-8
'''
Created on 26/05/2013
Código fonte da questão 01 da lista 02 da disciplina Criptografia
@author: Vagner Clementino
    Este módulo implementa o 'Miller-Rabin probabilistic'     primality test
    conforme descrito no Cap. 4 do Handbook of Applied Cryptography,disponível
    e disponível em http://www.cacr.math.uwaterloo.ca/hac/index.html
    Utilizou-se durante a implementaçao a mesma nomeclatura para as variáveis.
    Segue abaixo o pseudocódigo do algoritmo de Miller-Rabin
        MILLER-RABIN(n,t)
        INPUT: an odd integer n ≥ 3 and security parameter t ≥ 1.
        OUTPUT: an answer “prime” or “composite” to the question: “Is n prime?”
        1. Write n − 1 = 2s r such that r is odd.
        2. For i from 1 to t do the following:
        2.1 Choose a random integer a, 2 ≤ a ≤ n − 2.
        2.2 Compute y = ar mod n using Algorithm 2.143.
        2.3 If y = 1 and y = n − 1 then do the following:
        j←1.
        While j ≤ s − 1 and y = n − 1 do the following:
        Compute y←y 2 mod n.
        If y = 1 then return(“composite”).
        j←j + 1.
        If y = n − 1 then return (“composite”).
        3. Return(“prime”).
'''
import random

def int_to_string_bin(n):
    '''
        Retorna um string que representa a string binaria de um número
    '''
    return "{0:b}".format(n)

def exp_mod_n(a, k , n):
    '''
        Metódo que retorna a ^ k mod n, conforme pseudocodigo a seguir:
            1. Set b←1. If k = 0 then return(b).
            2. Set A←a.
            3. If ko = 1 then set b←a.
            4. For i from 1 to t do the following:
            4.1 Set A ←A ^ 2 mod n.
            4.2 If ki = 1 then set b←A· b mod n.
            5. Return(b).
    '''
    string_binaria = int_to_string_bin(k)
    t = len(string_binaria)
    b = 1
    if k == 0:
        return b
    A = a
    if string_binaria[(t - 1)] == "1":
        b = a
    for i in range((t - 2), -1, -1):
        A = ((A * A) % n)
        if string_binaria[i] == "1":
            b = ((A * b) % n)
    return b
    
     

def get_rs(n):
    '''
        Metódo que retorna um tupla (r,s), dado um inteiro n,
        onde (n − 1) = (2^s * r)
    '''
    m = (n - 1)
    s = 0
    r = 0
    
    while True:
        if m % 2 == 0:
            m = m / 2
            s += 1
            if m % 2 == 1:
                r = long(m)
        else:
            break
    tupla_rs = (r, s)
    return tupla_rs

def miller_rabin_prime_teste(n, t):
    '''
        Verifica se um número é primo utilizando o algoritmo de 
        Miller-Rabin
    '''
    tupla_rs = get_rs(n)
    r = long(tupla_rs[0])
    s = tupla_rs[1]
    
    for i in xrange(0, t):
        a = long(random.randint(2, (n - 2)))
        # Calculando y = (pow(a,r) % n) utilizando o laço for a seguir
        y = exp_mod_n(a, r, n)        
        
        if y != 1 and y != (n - 1):
            j = 1
            while j <= (s - 1) and y != (n - 1):
                y = exp_mod_n(y, 2, n)
                if(y == 1):
                    return False
                j += 1
            if y != (n - 1):
                return False
    return True
                
    
